package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 */

/**
 * 需要注意的是 candidates 中有重复元素，但是每个元素又只能使用一次
 * 因此
 * 1. 首先对 candidates 进行排序，让重复元素都相邻在一起
 * 2. 采用 used 数组来记录元素使用情况：初始化时，used 数组中的元素都为0，表示所有元素都没有使用过，一旦元素被采用，used 数组的值为 1
 *    我们 进行去重时，其实是对回溯的树形结构的每一层进行去重，在树形结构的树枝上是允许出现重复元素的（因为 candidates 中就是存在重复元素）
 *    在每一层中，如果前面一个元素使用过了，那么后面那个重复的元素依旧可以再次使用
 *              如果前面一个元素没有使用过，那么后面重复元素就不能被使用，否则必定会造成重复
 *              used[i - 1] == 1，说明同一树枝candidates[i - 1]使用过，在一个树枝上，也就是在一个回溯上，还没有走到底，used 不会回溯
 *              used[i - 1] == 0，说明同一树层candidates[i - 1]使用过，used已经回溯了，代表已经记录了之前的结果
 */

public class CombinationSumII {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            int[] used = new int[candidates.length];
            backtracking(candidates, target, used, 0, 0);
            return res;
        }

        private void backtracking(int[] candidates, int target, int[] used, int startIndex, int sum){
            if(sum >= target){
                if(sum == target) res.add(new ArrayList<>(path));
                return;
            }

            for(int i = startIndex; i < candidates.length; i++){
                if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == 0) continue;
                path.add(candidates[i]);
                used[i] = 1;
                backtracking(candidates, target, used, i+1, sum+candidates[i]);
                path.remove(path.size()-1);
                used[i] = 0;
            }
        }
    }
}
